1. Field of the Invention
The present invention relates to a router, and more particularly, to a method for forming a database to route a data packet from a plurality of prefixes and a method for routing and a router using the method thereof. The present application is based on Korean Patent Application No. 2000-49932, which is incorporated herein by reference.
2. Description of the Related Art
At the present time, generally, most data networks have a packet net based on IP (Internet Protocol). The respective packets in the packet net have information about the sender and receiver on a header thereof. By analyzing the information on the header of the packet, a transmission path is determined, which is called routing. A switching apparatus that performs the routing operation such as a router and a layer three switch is generally called a routing apparatus. Here, the routing apparatus is called the router for the convenience of explanation.
FIG. 1 is a view showing a construction of the system in which the router is adopted. A plurality of user's computers 10, 12, and 14 are connected to Internet 20 through a hub 16 and a router 18. Due to the very high transmission speed of a packet accompanied by a development of the transmission technology, the router is not capable of determining the transmission path with the header information in response to the speed of the transmitted packet in the Internet, which has a hierarchical address system, which may cause a problem of a speed bottleneck.
Also, due to the increase of the number of networks and hosts accompanied by a rapid development of the Internet, the number of existing IPv4 (IP version 4) addresses is running short. As a result, the routing between the networks is based on the CIDR (Classless InterDomain Routing) which does not classify the class B and the class C networks, and the prefixes for the routing are distributed at diverse lengths.
Accordingly, a longest matching prefix method is used to search for the most suitable routing path. The longest matching prefix method is a lookup method that, when there is more than one prefix matching with an individual address, selects the best matching prefixes.
The basic concept of a prefix expansion is described with reference to FIG. 2.
FIG. 2 shows an example of a prefix expansion, in which the prefixes are mapped into bit strings of reference length 4. Here, the prefix 01 and the prefix 011 have information A and D, respectively.
The bit strings of length 4 may have sixteen (16) possible prefixes. Only four (4) prefixes of 0100, 0101, 0110, 0111 among the sixteen (16) prefixes have a meaningful value, and respective values correspond to a value of the prefix which is close to a reference row.
Next, a prefix expansion table formed from a prefix table by making use of such prefix expansion will be described.
FIG. 3A shows an example of an original prefix table. The prefixes 01, 1, 0011, 011, 100, and 110 have information A, B, C, D, E, and F, respectively. FIG. 3B shows the prefix expansion table formed from the prefix table of FIG. 3A into the reference length of 4 bits.
As shown in FIG. 3B, a prefix expansion table is formed by mapping the prefixes into the reference length 4, which is the length of the longest bit string. The prefixes that do not include information are given a value of NULL.
While the information lookup under a tree type data structure must refer to the memory in every step, according to the structure transformed into the prefix expansion table, it is possible to obtain the desired information by only one reference to memory, i.e., without requiring reference to memory in every step.
However, while there are six (6) entries in the original prefix table, there are sixteen (16) entries in the prefix expansion table. As a result, the capacity of the memory has to be increased, causing cost increase.
Next, the prefix table formed to have a tree structure will be described.
FIG. 4A shows another example of a prefix table, and FIG. 4B shows a prefix tree formed from the prefix table of FIG. 4A by making use of a binary tree. The prefix tree of FIG. 4B has depth of 8.
Generally, the binary tree forms a tree in a manner such that the binary tree starts at the root from the most significant bit of the prefix, and if the value of the bit is 0, moves to the left, one node at a time, and if the value of the bit is 1, moves to the right, one node at a time.
At this time, the last leaf becomes a prefix node which has information, i.e., the last leaf becomes a meaningful prefix node. The middle nodes, which exist from the root to the last leaf, may be a meaningful prefix node or a meaningless prefix node which does not have information.
In the lookup operation for searching for a desired IP address, performance of the lookup operation depends on the number of the middle nodes, which are needed to search for the desired prefix, and the capacity of the memory depends on the number of total nodes. Accordingly, it is critical to decrease the depth of the tree.